package TenkindsOfAlgorithm.patternMatch;
/**
 * 时间复杂度 O(n+m) .
 */

import java.util.ArrayList;
import java.util.List;

public class kmp {
    public static void main(String[] args) {
        String p = "ABABCABAB";
        int[] next = new int[p.length()];
        getPrefixTable(p,next);
        getNext(next);
        for (int i = 0; i < next.length; i++) {
            System.out.println(next[i]);
        }
        System.out.println(kmpSearch("ABABABABCABABABABCABAB", p, next));
    }

    /**
     * kmp
     */
    public static List<Integer> kmpSearch(String s1, String p1, int []next){
        ArrayList<Integer> list = new ArrayList<>();
        char[] s = s1.toCharArray();
        char[] p = p1.toCharArray();
        int i =0;
        int j = 0;
        while (i<s.length && j<p.length){
            if (s[i]==p[j]){
                i++;
                j++;
            }else {
                // 灵魂
                j = next[j];
            }
            // 这里是处理多匹配问题 使用集合装入下标
            if (j== p.length-1 && s[i]==p[j]){ // 找到了 匹配完毕
                list.add(i-j+1);
                i++;
                j = next[j];
                j++;
            }
        }
        return list;
    }
    /**
     * len 表示含自身最长公共前后缀长度
     */
    public static void getPrefixTable(String p, int[] next) {
        char[] pattern = p.toCharArray();
        next[0] = 0;
        for (int i = 1; i < pattern.length; i++) {
            int k = next[i-1];
            // 不断递归寻找子对称 , k=0之后说明不会再有子对称
            while (pattern[i]!=pattern[k] && k>0){
                k = next[k-1];
            }
            if (pattern[i]==pattern[k]){
                next[i] = k+1;
            }else {
                next[i] = 0;
            }
        }
    }
    public static void getNext(int []preTable){
        for (int i = preTable.length-1; i >0 ; i--) {
            preTable[i] = preTable[i-1];
        }
        preTable[0] = -1;
    }

}
